package sort

import (
//    "fmt"
//    "sort"
)


// Some definitions so that we can simply sort
type Array []int
func (a Array) Len() int {
    return len(a)
}
func (a Array) Less(i, j int) bool {
    return a[i] < a[j]
}
func (a Array) Swap(i, j int) {
    a[i], a[j] = a[j], a[i]
}

type Sortable interface {
    Len() int
    Less(i, j int)
    Swap(i, j int)
}

// Common insertion sort
func (s Array) InsertionSort() {
    for i := 0; i < s.Len(); i++ {
        val, j := s[i], i-1
        for ; j >= 0; j-- {
            if val < s[j] {
                // Move over 
                s[j+1] = s[j]
            } else {
                break
            }
        }
        s[j+1] = val
    }
}

// Median for QuickSort
func Median(t Array) (val, index int) {
    size := t.Len()
    a, b, c := t[size/4], t[size/2], t[(3*size)/4]
    switch {
    case a<=b && b<=c:
    case c<=b && b<=a:
        return b, size/2
    case b<=a && a<=c:
    case c<=a && a<=b:
        return a, size/4
    default:
    }
    return c, (3*size)/4
}
